import { LinkedList, Node } from "./linkedList";

export class DoublyNode<T> extends Node<T> {
  prev: DoublyNode<T> | null;
  head: DoublyNode<T> | null;
  constructor(data: T) {
    super(data);
    this.prev = null;
    this.head = null;
  }
}

export class DoublyLinkedList<T> extends LinkedList<T> {
  tail: DoublyNode<T> | null;
  constructor() {
    super();
    this.tail = null;
    this.head = null;
  }

  append(data: T) {
    const newNode = new DoublyNode(data);
    if (this.length === 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail!.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.length++;
  }

  insert(index: number, data: T) {
    if (index < 0 || index > this.length) return false;
    const newNode = new DoublyNode(data);
    if (index === 0) {
      if (this.length === 0) {
        this.head = newNode;
        this.tail = newNode;
      } else {
        newNode.next = this.head;
        (this.head as DoublyNode<T>).prev = newNode;
        this.head = newNode;
      }
    } else if (index === this.length) {
      newNode.prev = this.tail;
      this.tail!.next = newNode;
      this.tail = newNode;
    } else {
      let index = 0;
      let current = this.head;
      while (index < index) {
        current = current?.next!;
      }
      newNode.prev = (current as DoublyNode<T>).prev;
      newNode.next = current;
      ((current as DoublyNode<T>).prev as DoublyNode<T>).next = newNode;
      (current as DoublyNode<T>).prev = newNode;
    }
    this.length++;
    return newNode;
  }

  getData(position: number) {
    if (position < 0 || position >= this.length) return null;
    if (this.length / 2 >= position) {
      let index = 0;
      let current = this.head as DoublyNode<T>;
      while (index++ < position) {
        current = current.next as DoublyNode<T>;
      }
      return current!.data;
    } else {
      let index = this.length - 1;
      let current = this.tail as DoublyNode<T>;
      while (index-- > position) {
        current = current.prev as DoublyNode<T>;
      }
      return current.data;
    }
  }

  removeAt(position: number) {
    // 1、position越界判断
    if (position < 0 || position >= this.length) return null;

    // 2、删除指定 position 节点
    let current = this.head as DoublyNode<T>;

    // 删除第一个节点的情况
    if (position === 0) {
      // 链表内只有一个节点的情况
      if (this.length === 1) {
        this.head = null;
        this.tail = null;
      } else {
        // 链表内有多个节点的情况
        (this.head!.next! as DoublyNode<T>).prev = null;
        this.head = this.head!.next;
      }
    } else if (position === this.length - 1) {
      // 删除最后一个节点的情况
      current = this.tail!;
      (this.tail!.prev as DoublyNode<T>).next = null;
      this.tail = this.tail!.prev;
    } else {
      // 删除 0 ~ this.length - 1 里面节点的情况

      // 判断要删除的节点离头尾节点哪个比较近

      // 离头节点比较近
      if (this.length / 2 >= position) {
        // 获取指定 position 的节点
        let index = 0;
        while (index++ < position) {
          current = current.next as DoublyNode<T>;
        }

        // 删除相应节点
        (current!.prev as DoublyNode<T>).next = current!.next;
        (current!.next as DoublyNode<T>).prev = current.prev;
      } else {
        // 离尾节点比较近

        // 获取指定 position 的节点
        let index = this.length - 1;
        current = this.tail!;
        while (index-- > position) {
          current = current.prev!;
        }

        // 删除相应节点
        current!.prev!.next = current.next;
        (current!.next as DoublyNode<T>).prev = current.prev;
      }
    }

    // 3、更新链表长度 -1
    this.length--;
    // 4、返回被删除的节点，方便其他操作
    return current;
  }

  backwardString() {
    let current = this.tail;
    let str = "";
    while (current) {
      str += current.data + "--";
      current = current.prev;
    }
    return str;
  }
}
